package com.example.demo.leetcode.zuocheng.graph;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;


/**
 * @author xujm
 * @version V2.4
 *  求任意一个点到所有点的最小距离
 * 算法思路:
 *         一个map，存放起始点到其他所有点的距离，初始吧起始点A放入
 *         一个unselectSet, 存放已经被使用过的点
 *
 *         循环:
 *         每次从distancemap中取出，距离最小的，并且没有使用过的节点X
 *         遍历X节点的所有边，
 *         每个边指向Y节点： 根据map.get(Y), map.get(X) + X.to.width 比较，小的那个成为抵达Y节点的最小值，存入map
 *
 *         map中所有边取完，循环结束，map 则为起始点A到其他点的最小距离
 *
 * 算法优化1: 使用堆结构进行优化,时间复杂度从O(N),降低到logN
 *            堆结构:
 *            Node []   数组存放堆的数据
 *            indexMap<Node,Integer> 表示每个Node在数组中的下标，如果pop出去的数置为-1，表示进来过，下次遇到忽略(因为弹出的数已经遍历过)
 *            distanceMap<Node,Integer> 标识每个node离开始节点的距离，每次有更小的数，需要更新(insertHeapfiy)
 *            size 标识堆大小
 *
 *
 * @since 2.4.0 2021/8/15 11:23
 */
public class Node_Djstla算法 {


    public  static Node initNode(){

        HashMap<String,Node> map = new HashMap<>();
        String [][] arr ={{"A","B","1"},{"A","C","2"},{"B","D","4"},{"C","D","2"}};

        for(int i =0 ;i<arr.length;i++){

            String [] temp=arr[i];
            Node from = map.get(temp[0]+"") == null ?  new Node(temp[0]+"") : map.get(temp[0]+"");
            Node to = map.get(temp[1]+"") == null ?  new Node(temp[1]+"") : map.get(temp[1]+"");
            from.out++;
            to.in++;

            Edge edge = new Edge(Integer.parseInt(temp[2]),from,to);

            from.edges.add(edge);
            from.nexsts.add(to);

            map.put(from.value,from);
            map.put(to.value,to);
        }

        return map.get("A");
    }

    /**
     *  常规dijistla算法
     * @return
     */

    public static HashMap<Node,Integer> djstla(){
        Node node = initNode();
        HashMap<Node,Integer> distanceMap = new HashMap<>();
        HashSet<Node> unselectSet = new HashSet<>();

        distanceMap.put(node,0);
        Node start = getMinDistanceUnselectNode(distanceMap,unselectSet);

        while(start != null){

            int distance = distanceMap.get(start);
            ArrayList<Edge> edges = start.edges;
            for(Edge edge : edges){

                if(!distanceMap.containsKey(edge.to)){
                    distanceMap.put(edge.to , distance + edge.weight);
                }else{
                    distanceMap.put(edge.to, Math.min(distanceMap.get(edge.to), distance + edge.weight));
                }
            }
            start = getMinDistanceUnselectNode(distanceMap,unselectSet);
        }
        return distanceMap;
    }

    public static Node getMinDistanceUnselectNode(HashMap<Node,Integer> distanceMap,HashSet<Node> unselectSet){
        // 获取没有遍历过的节点
        int mindistance = Integer.MAX_VALUE;
        Node node = null;
        for(Map.Entry<Node,Integer> entry : distanceMap.entrySet()){
            if(!unselectSet.contains(entry.getKey()) &&  entry.getValue() < mindistance){
                mindistance = entry.getValue();
                node = entry.getKey();
            }
        }
        unselectSet.add(node);
        return node;
    }







    static class NodeRecord{

        Node node;
        int distance;

        public NodeRecord(Node node, int distance) {
            this.node = node;
            this.distance = distance;
        }
    }

    static class NodeHeap{


        Node [] arr;
        HashMap<Node,Integer> indexMap;
        HashMap<Node,Integer> distanceMap;
        int index;

        public NodeHeap(int maxSize){
            arr = new Node[maxSize];
            indexMap = new HashMap<Node,Integer>();
            distanceMap = new HashMap<Node,Integer>();
            index = 0;
        }


        public boolean isEmpty(){
            if(index == 0){
                return true;
            }
            return false;
        }


        public void addOrUpdateOrIngore(Node node,int distance){
            //在堆上
            if(inHeap(node)){
                //如果distance小于原来的更新
                if(distance < distanceMap.get(node)){
                    distanceMap.put(node,distance);
                    //重新向上或者向下
                    insertHeapfiy(node);
                    heapFiy(node);
                }
            }
            //没进来过
            if(!entered(node)){
                arr[index] = node;
                indexMap.put(node,index++);
                distanceMap.put(node,distance);
                //重新向上
                insertHeapfiy(node);
            }
            //不在堆上，进来过
            return;
        }

        //向上遍历 找比自己大的
        public void insertHeapfiy(Node node){

            Integer nodeIdx = indexMap.get(node);
            Integer parentIdx = (nodeIdx -1)/2;
            Node parentNode = arr[parentIdx];
            Integer distance = distanceMap.get(parentNode);
            while(nodeIdx >=0 && parentIdx>=0 && distanceMap.get(node) < distance ){
                swap(node,parentNode);

                nodeIdx = indexMap.get(node);
                parentIdx = (nodeIdx -1)/2;
                parentNode = arr[parentIdx];
                distance = distanceMap.get(parentNode);
            }

        }

        public void swap(Node node,Node parentNode){
            Integer nodeIdx = indexMap.get(node);
            Integer parentIdx = indexMap.get(parentNode);
            arr[nodeIdx] = parentNode;
            arr[parentIdx] = node;
            indexMap.put(node,parentIdx);
            indexMap.put(parentNode,nodeIdx);

        }


        //向下遍历 找比自己小的
        public void heapFiy(Node node){

            Integer nodeIdx = indexMap.get(node);
            while(nodeIdx < index){

                int left = 2 * nodeIdx + 1 < index ? 2 * nodeIdx + 1 : index;
                int right = left + 1 < index?  left+1 : index;
                int lest = distanceMap.get(arr[left]) < distanceMap.get(arr[right]) ? left : right;
                if(lest == index){
                    return;
                }
                if(distanceMap.get(node) < distanceMap.get(arr[lest])){
                    return;
                }

                Node sonNode = arr[lest];
                swap(node,sonNode);

            }


        }




        public boolean entered(Node node){
            if(indexMap.containsKey(node)){
                return true;
            }
            return false;
        }


        public boolean inHeap(Node node){
            if(indexMap.containsKey(node) && indexMap.get(node) != -1){
                return true;
            }
            return false;
        }



        //弹出堆顶的最小值
        public NodeRecord pop(){

            swap(arr[0],arr[--index]);
            heapFiy(arr[0]);
            Node result = arr[index];
            indexMap.put(result,-1);
            NodeRecord record = new NodeRecord(result,distanceMap.get(result));
            return record;

        }
    }



    /**
     * digistla 算法优化
     * @return
     */
    public static HashMap<Node,Integer> djstla2(){

        Node node = initNode();

        NodeHeap nodeHeap = new NodeHeap(100);

        nodeHeap.addOrUpdateOrIngore(node,0);

        HashMap<Node,Integer> resultMap = new HashMap();

        while(!nodeHeap.isEmpty()){

            NodeRecord record = nodeHeap.pop();
            Node miniNode = record.node;
            int distance = record.distance;

            for(Edge edge : miniNode.edges){
                nodeHeap.addOrUpdateOrIngore(edge.to,edge.weight+distance);
            }

            resultMap.put(miniNode,distance);
        }

        return resultMap;
    }


    public static void main(String[] args) {
        HashMap<Node, Integer> map = djstla();

        for(Map.Entry<Node,Integer> entry : map.entrySet()){
            System.out.println(entry.getKey().value+":"+entry.getValue());
        }

    }





}
